package leetcode.editor.cn;
//现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 
//prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。 
//
// 
// 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。 
// 
//
// 返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。 
//
// 
//
// 示例 1： 
//
// 
//输入：numCourses = 2, prerequisites = [[1,0]]
//输出：[0,1]
//解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
// 
//
// 示例 2： 
//
// 
//输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
//输出：[0,2,1,3]
//解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
//因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。 
//
// 示例 3： 
//
// 
//输入：numCourses = 1, prerequisites = []
//输出：[0]
// 
//
// 
//提示：
//
// 
// 1 <= numCourses <= 2000 
// 0 <= prerequisites.length <= numCourses * (numCourses - 1) 
// prerequisites[i].length == 2 
// 0 <= ai, bi < numCourses 
// ai != bi 
// 所有[ai, bi] 互不相同 
// 
//
// Related Topics 深度优先搜索 广度优先搜索 图 拓扑排序 👍 762 👎 0


import java.util.*;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution105 {

    boolean[] visited;
    boolean[] onPath;
    boolean hasCycle = false;
    // 记录后序遍历结果
    List<Integer> postorder = new ArrayList<>();


    /**
     * DFS
     * 很显然，如果一幅有向图中存在环，是无法进行拓扑排序的，因为肯定做不到所有箭头方向一致；
     * 反过来，如果一幅图是「有向无环图」，那么一定可以进行拓扑排序。
     *
     * 但是我们这道题和拓扑排序有什么关系呢？
     *
     * 其实也不难看出来，如果把课程抽象成节点，课程之间的依赖关系抽象成有向边，那么这幅图的拓扑排序结果就是上课顺序。
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 将后序遍历的结果进行反转，就是拓扑排序的结果。
        List<Integer>[] graph = buildGraph(numCourses, prerequisites);
        visited = new boolean[numCourses];
        onPath = new boolean[numCourses];
        for (int i = 0; i < numCourses; i++) {
            // 后续
            transfer(i, graph);
        }
        // 有环就还会空数组
        if (hasCycle) {
            return new int[0];
        }

        // 逆后序遍历结果即为拓扑排序结果
        Collections.reverse(postorder);
        int[] res = new int[postorder.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = postorder.get(i);
        }
        return res;
    }



    /**
     * BFS
     *
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public int[] findOrder1(int numCourses, int[][] prerequisites) {
        // 将后序遍历的结果进行反转，就是拓扑排序的结果。
        List<Integer>[] graph = buildGraph(numCourses, prerequisites);
        int[] res = new int[numCourses];

        // 构建入度数组
        int[] inDegree = new int[numCourses];
        for (int[] prerequisite : prerequisites) {
            int from = prerequisite[1];
            int to = prerequisite[0];
            inDegree[to]++;
        }

        // 根据入度初始化队列中的节点
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < inDegree.length; i++) {
            if (inDegree[i] == 0) {
                q.offer(i);
            }
        }

        // 经历的节点
        int count = 0;
        while (!q.isEmpty()) {
            Integer curr = q.poll();
            res[count] = curr;
            count++;
            for (Integer next : graph[curr]) {
                inDegree[next]--;
                if (inDegree[next] == 0) {
                    q.offer(next);
                }
            }
        }

        if (count != numCourses) {
            return new int[]{};
        }

        return res;
    }



    private void transfer(int i, List<Integer>[] graph) {
        // 同一条路径中访问到同一个节点
        if (onPath[i]) {
            hasCycle =true;
        }
        // 其它路径访问到了已访问过的路径或者已经存在环
        if (visited[i] || hasCycle) {
            return;
        }
        // 前序位置
        visited[i] = true;
        onPath[i] = true;
        for (Integer v : graph[i]) {
            transfer(v, graph);
        }
        // 后序位置
        postorder.add(i);
        onPath[i] = false;

    }

    private List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph = new LinkedList[numCourses];
        for (int i = 0; i < graph.length; i++) {
            graph[i] = new LinkedList<>();
        }
        for (int[] prerequisite : prerequisites) {
            int to = prerequisite[0];
            int from = prerequisite[1];
            graph[from].add(to);
        }
        return graph;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
